package com.example;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author loubobooo
 * @Description #103. 二叉树的锯齿形层序遍历
 * @Date 2022/2/24
 */
public class BinaryTreeZigzagLevelOrderTraversal {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    List<List<Integer>> list = new LinkedList<>();

    /**
     * 方法描述:给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     * @param: [root]
     * @return: java.util.List<java.util.List<java.lang.Integer>>
     * @author: loubobooo
     * @date: 2022/2/24
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return list;
        }
        bfs(root, 0);
        return list;
    }

    private void bfs(TreeNode node, Integer level) {
        if (node == null) {
            return;
        }
        if (level == list.size()) {
            // 先存入空数组
            list.add(new ArrayList<>());
        }
        // 奇数
        if ((level & 1) == 1) {
            // 拿到空数组，并存入元素，插到头部
            list.get(level).add(0, node.val);
        } else {
            // 插入到尾部
            list.get(level).add(node.val);
        }
        // 广度优先遍历
        bfs(node.left, level + 1);
        bfs(node.right, level + 1);
    }
}
